home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part2 / 14094 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  1.7 KB
  1. Path: anvil.ugrad.cs.ubc.ca!not-for-mail
  2. From: c2a192@ugrad.cs.ubc.ca (Kazimir Kylheku)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: fast find algorithm
  5. Date: 11 Apr 1996 12:00:36 -0700
  6. Organization: Computer Science, University of B.C., Vancouver, B.C., Canada
  7. Message-ID: <4kjkskINNmf9@anvil.ugrad.cs.ubc.ca>
  8. References: <Dp8wE6.8DG@cix.compulink.co.uk> <4kbrg8$luu@druid.borland.com> <316B2716.4993@airmail.net> <4kjahn$jp2@druid.borland.com>
  9. NNTP-Posting-Host: anvil.ugrad.cs.ubc.ca
  10.  
  11. In article <4kjahn$jp2@druid.borland.com>,
  12. Pete Becker <pete@borland.com> wrote:
  13.  >In article <316B2716.4993@airmail.net>, markn@airmail.net says...
  14.  >>
  15.  >>Pete Becker wrote:
  16.  >>> 
  17.  >>>     If you use a linked list at each array location to resolve conflicts 
  18.  >then
  19.  >>> you can delete elements.
  20.  >>
  21.  >>Knuth gives an algorithm for deleting elements from a table when using linear 
  22.  >pr
  23.  >>obing, 
  24.  >>and it's pretty easy to see how that would work.  I'm not sure there is a 
  25.  >practi
  26.  >>cal 
  27.  >>way to remove elements when using a secondary hash probe...
  28.  >
  29.  >Good point: with linear probing you know where the next location is, and sooner 
  30.  >or later you know that you're done. My guess is that deleting would be constant 
  31.  >time in most cases, but O(n) worst case, where n is the size of the table.
  32.  
  33. The way you delete elements from a hash table is that instead of making a
  34. vacant spot of a deleted item, you put in a ``tombstone''. When probing for a
  35. subsequent insertion, when you come upon the tombstone, you place the new
  36. element there, but when searching for an existing element, you skip over the
  37. tombstone and keep probing.
  38.  
  39. This way you can use good probing functions that cycle through all the residues
  40. modulo the table size without searching linearly and introducing primary
  41. clustering.
  42. -- 
  43.  
  44.